package 组合问题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 组合总和 III
 * 找出所有相加之和n 的k个数的组合，且满足下列条件：
 * 只使用数字1到9
 * 每个数字最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 *
 * @date 2022/11/13 14:47
 */
public class Demo216 {
    public static void main(String[] args) {
        res= combinationSum3(9, 45);
        System.out.println(res);
    }
    static List<List<Integer>> res=new ArrayList<>();

    static List<Integer> singPath=new LinkedList<>();
    static int sum=0;
    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> singPath= new LinkedList<>();
        backTrack(k,n,1);
        return res;
    }

    private static void backTrack(int k, int n, int index) {
        if(singPath.size()==k){

            if(sum==n){
                res.add(new ArrayList<>(singPath));
            }
            return;
        }
        //裁剪
        for (int j = index; j <=9-(k- singPath.size())+1 ; j++) {
            sum=sum+j;
            singPath.add(j);
            backTrack(k,n,j+1);
            singPath.remove(singPath.size()-1);
            sum=sum-j;
        }
    }
}
